#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int left = 0;
    int right = 0;
    int n = 0;
    vector<string> ret;
    string path;
    vector<string> generateParenthesis(int _n) {
        n = _n;
        dfs();
        return ret;
    }

    void dfs()
    {
        if (right == n)
        {
            ret.push_back(path);
            return;
        }

        if (left < n)
        {
            left++;
            path += "(";
            dfs();
            left--;
            path.pop_back();
        }

        if (right < left)
        {
            right++;
            path += ")";
            dfs();
            right--;
            path.pop_back();
        }
    }
};